This invention relates to a technique for determining a location in space. More particularly, the invention is related to technology associated with touch screen displays and is the basis for determining location of a contact on a touch screen display. In a more general sense, the underlying technology of the invention can be applied to the determining of a location in multi-dimensional space, where some of the dimensions relate to parameters other than physical location.
By way of theoretical background, an array of N vectors denoted (XV[1:N]), in an L-dimensional space is a collection of unique signatures which identify a specific characterized system. An example of a system according to the field of invention is a characterization of a touch screen display having N distinguishable touch locations on a two-dimensional display screen. A sample vector (XS) in L-dimensional space, each sample in the vector representing a dimension, is presented as an input from a pair of sensors on each edge of the display to the search subsystem to identify the closest match to the array of N unique signatures. A sample vector typically consists of one of the vectors in the array with additive white noise in each of L dimensions uniformly distributed in the range [−e,e]. The coefficient ‘e’ is referred to as a noise-splatter coefficient and is typically expressed as a percentage of the dynamic range M of each dimension. The closest match XVM to the sample vector XS is defined as one which has the lowest “score” S of all elements in the array, XV[1:N], where the score is defined as
            S      ⁡              [        i        ]              =                  ∑                  j          =          1                L            ⁢                                                                            XV                ⁡                                  [                  i                  ]                                            ⁡                              [                j                ]                                      -                          XS              ⁡                              [                j                ]                                                              n              ,            where      ⁢                          ⁢      n      ⁢                          ⁢      is      ⁢                          ⁢      an      ⁢                          ⁢      integer      ⁢                          ⁢      XVM        =          XV      ⁡              [        k        ]              ,      k    =          Index      ⁢                          ⁢      of      ⁢                          ⁢      min      ⁢                        {                      S            ⁡                          [              i              ]                                }                          i          =          1                          i          =          N                    
It is already known that this match is achieved by computing the scores for all the array elements and then picking the minimum value. A key requirement is that computing the scores for all vectors is necessary, since each dimension is equally important. This process of computing scores for all the vectors with respect to the sample involves accessing the entire array of N vectors in all the L dimensions every time a new sample arrives. Hence, arriving at a signature match for every new sample requires N×L memory accesses, (N×L) subtractions, (N×(L−1)) additions and (n−1)×N×L multiplications, which is slow and certainly burdensome task.
An exhaustive search such as this to find a match places significant restrictions on the response time to locate a match due to high memory access and computational requirements which grows exponentially with the array length (N) and vector dimension (L). What is needed is a technique for accelerating and streamlining this processing to improve the performance of a touch screen display.